/**
 * 
 */
package linkedlist.passed2;

/**
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
 */
public class ReorderList {

	/**
	 * Definition for singly-linked list.
	 */
	class ListNode {
		int val;
	    ListNode next;
	    ListNode(int x) {
	    	val = x;
	    	next = null;
	    }
	}
	
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        ListNode slow = head;
        ListNode fast = head.next;
        //pitfall make sure slow.next is the head of 2nd half
        while (fast != null && fast.next != null) {
        	slow = slow.next;
        	fast = fast.next.next;
        }
        ListNode head2 = slow.next;
        slow.next = null;
        
        head2 = reverse(head2);
        
        while (head != null) {
        	ListNode next = head.next;
        	head.next = head2;
        	head = head.next;
        	head2 = next;
        }
    }	
    
    private ListNode reverse(ListNode head) {
    	ListNode newHead = null;
    	while(head != null) {
    		ListNode next = head.next;
    		head.next = newHead;
    		newHead = head;
    		head = next;
    	}
    	return newHead;
    }
    
    private void merge(ListNode head1, ListNode head2) {
    	if (head1 == null) return;
    	if (head2 == null) return;
    	
    	ListNode dummyHead = new ListNode(-1);
    	ListNode currNode = dummyHead;
    	while (head1 != null && head2 !=null ) {
    		currNode.next = head1;
    		currNode = currNode.next;
    		head1 = head1.next;
    		currNode.next = head2;
    		currNode = currNode.next;
    		head2 = head2.next;
    	}
    	if (head1 == null) currNode.next = head2;
    	if (head2 == null) currNode.next = head1;
    }
	
	/**
	 * 
	 */
	public ReorderList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
